package cn.edu.jxau.test;

/**
 * 基于大顶堆的优先队列：max priority queue
 * 
 * @author 付大石
 */
public class MaxPQ {

    public static void main(String[] args) {

        MaxPQ maxPQ = new MaxPQ(10);
        System.out.println(maxPQ);
        maxPQ.insert(80);
        maxPQ.insert(81);
        maxPQ.insert(69);
        System.out.println(maxPQ + "  " + maxPQ.delMax());
        maxPQ.insert(88);
        maxPQ.insert(65);
        maxPQ.insert(77);
        System.out.println(maxPQ + "  " + maxPQ.delMax());
        maxPQ.insert(80);
        maxPQ.insert(76);
        maxPQ.insert(69);
        System.out.println(maxPQ + "  " + maxPQ.delMax());
    }

    private int[] pq; // priority queue
    private int size;

    public MaxPQ(int size) {
        pq = new int[size + 1];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void insert(int i) {

        pq[++size] = i;
        swim(size);
    }

    /**
     * dekete max，删除堆顶元素
     * 
     * @return
     */
    public int delMax() {

        if (isEmpty()) {
            throw new RuntimeException("优先队列已空");
        }
        int max = pq[1];
        swap(1, size);
        sink(1);
        size--;
        return max;
    }

    /**
     * 交换优先队列中索引{@code i}和索引{@code j}的元素
     * 
     * @param i
     * @param j
     */
    private void swap(int i, int j) {

        int temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    /**
     * 下沉构造堆
     * 
     * @param k
     */
    private void sink(int k) {
        
        int target = pq[k]; //需要下沉的元素
        while (2 * k <= size) {
            int i = 2 * k;
            if (i < size && pq[i] < pq[i + 1]) { // 找出子元素中的最小值
                i++;
            }
            if (target >= pq[i])
                break;
            pq[k] = pq[i];
            k = i;
        }
        pq[k] = target;
    }

    /**
     * 上浮构造堆
     * 
     * @param k
     */
    private void swim(int k) {

        int target = pq[k]; //需上浮的元素
        while (k > 1 && target > pq[k / 2]) {
            pq[k] = pq[k / 2];
            k /= 2;
        }
        pq[k] = target;
    }

    @Override
    public String toString() {

        StringBuilder builder = new StringBuilder();
        builder.append("size:").append(size).append("\t");
        builder.append("[");
        for (int i = 1; i <= size; i++) {
            builder.append(pq[i]).append(",");
        }
        if (!isEmpty()) {
            builder.deleteCharAt(builder.length() - 1);
        }
        builder.append("]");
        return builder.toString();
    }
}